1. Field of the Invention
The present invention pertains to the field of rendering grayscale data on a binary marking engine such as are found in low cost digital copiers and printers. Specifically, the present invention pertains to the field of hardware support for halftone rendering and error diffusion rendering.
2. Discussion of the Related Art
Halftoning and error diffusion are two well-known algorithms for rendering color or black and white grayscale data on a binary marking engine. Many display and hardcopy devices are bilevelxe2x80x94they produce just two intensity levels, either xe2x80x9conxe2x80x9d or xe2x80x9coffxe2x80x9d.
In the technique known as halftoning, each small resolution unit of area in the rendered output is imprinted with black ink whose area is proportional to the blackness 1-I (where I is intensity) of the corresponding area in the original unrendered input. For example, a 2xc3x972 pixel area of a bilevel display can be considered the small resolution unit. In this case, each 2xc3x972 pixel area can be used to produce five different intensity levels at the cost of halving the spatial resolution along each axis. This result is accomplished by turning xe2x80x9conxe2x80x9d either none, 1, 2, 3, or all 4 of the four pixels in the small resolution unit. In general, an nxc3x97n group of bilevel pixels can provide n2+1 intensity levels but lowers the spatial resolution on each axis by a factor of 1/n.
In the technique known as error diffusion, the error between the rendered pixel value and the corresponding unrendered pixel value is computed. The error is added to the values of the four image-array pixels to the right of and below the pixel in question: 7/16 of the error to the pixel to the right, 3/16 to the pixel below and to the left, 5/16 to the pixel immediately below, and 1/16 to the pixel below and to the right. This has the effect of spreading, or diffusing, the error over several pixels in the image array.
Each of the halftone and error diffusion techniques has advantages in distinct situations. For example, it has been known in the art that error diffusion can have both superior tone response and detail rendition as compared to halftoning on high quality marking engines. Alternatively, for a lower quality marking engine in which dot gain and dot misregistration limit image quality, the clustered dot halftoning algorithm has been shown to somewhat mitigate the adverse effects of the lower print quality. Therefore, the specific marking engine to be used or the source material to be rendered may make one algorithm more suitable than the other.
It is therefore desirable to have the capability to perform either rendering technique. These rendering techniques are suitable for implementation in hardware, for example, on an integrated circuit. However, to implement two separate hardware renderers is expensive, especially given that one of the hardware renderers will be idle at any given time. As is apparent from the above discussion, a need exists for a lower cost hardware renderer capable of selectively performing either halftone or error diffusion rendering.
Conventional circuits for rendering color or black and white grayscale data on a binary marking engine operate either according to a halftoning algorithm or according to an error diffusion algorithm. Because each algorithm has its distinct advantages, it is desirable to implement a marking engine capable of functioning in either error diffusion mode or halftone mode. However, conventionally the duplicative hardware needed to implement both an error diffusion renderer and a halftone renderer is prohibitively expensive for many applications. An object of the present invention is to implement a circuit for rendering capable of operating in either an error diffusion mode or a halftone mode without unduly increasing the hardware cost of supporting both modes.
The present invention describes how one renderer serve as either a halftone renderer or an error diffusion renderer. Importantly, the more expensive portions of either rendererxe2x80x94the memory and memory bandwidthxe2x80x94are reused according to the present invention, so that the incremental cost of including an additional rendering algorithm is very low. According to the present invention, only one set of logic performs either halftoning or error diffusion rendering. Compared to conventional logic which performs only error diffusion, the incremental cost of implementing the combined halftoning/error diffusion renderer according to the present invention is very low.
According to the present invention, circuit implementations generate a rasterized rendered datastream from a rasterized unrendered datastream using either a halftone or error diffusion algorithm. Thus, the circuits according to the present invention are operable to function in either halftone mode or error diffusion mode.
The circuits according to the present invention include a comparator for comparing an unrendered pixel signal and a threshold signal regardless of whether or not the circuit is operating in halftone mode or error diffusion mode.
According to an aspect of the present invention, a pixel multiplexor selects between a rasterized unrendered pixel signal from an input rasterized unrendered datastream when in halftone mode and an error diffusion adjusted pixel signal generated by error diffusion hardware when in error diffusion mode. The error diffusion hardware which produces the error diffusion adjusted pixel signal includes an error diffusion adder which adds the rasterized unrendered pixel signal from the input rasterized unrendered datastream to an error diffusion feedback signal generated by an error diffusion filter. The error diffusion filter takes the unrendered pixel signal from the pixel multiplexor operating in error diffusion mode and the binary rasterized rendered output signal from the comparator as inputs. The difference between the binary rasterized rendered output signal and the unrendered pixel signal represents the total error which must be distributed to other pixels according to the error diffusion algorithm. The error diffusion filter produces the error diffusion feedback signal and a current error diffusion state signal as outputs. The error diffusion feedback signal represents error to be distributed to the subsequent pixel in the same scan line. The current error diffusion state signal represents error to be distributed to a pixel in the next scan line. Thus, the circuits according to the present invention include a memory for storing the current error diffusion state signal and for retrieving it as the previous error diffusion state signal during the processing of the appropriate pixel in the next scan line when operating in error diffusion mode. The error diffusion adder adds the previous error diffusion state signal from the memory and adds it to the rasterized unrendered pixel signal from the input rasterized unrendered datastream and the error diffusion feedback signal generated by an error diffusion filter to produce the error diffusion adjusted pixel signal.
According to another aspect of the present invention, a threshold multiplexor selects between an error diffusion threshold signal and a halftone threshold signal depending upon whether the circuit is operating in error diffusion mode or halftone mode. The threshold multiplexor passes the threshold signal which is selected to the comparator. The circuit preferably also includes an error diffusion threshold register to storing the error diffusion threshold signal.
According to yet another aspect of the present invention, an error diffusion write address generator provides an error diffusion write address signal which indicates the memory location in which to store the current error diffusion state signal computed by the error diffusion filter when the circuit is operating in error diffusion mode. When operating in halftone mode, the memory is operable to retrieve a halftone threshold signal which is supplied to the threshold multiplexor.
According to another aspect of the present invention, a read address generator provides a read address signal to the memory for indicating the memory location from which to read either the previous error diffusion state signal or the halftone threshold signal.
In an embodiment of the present invention, the read address generator includes a read address multiplexor for selecting between an error diffusion read address signal produced by an error diffusion read address generator and a halftone read address signal produced by a halftone read address generator depending upon the mode in which the circuit is operating.
In an alternative embodiment of the present invention, the read address generator includes a read address register which stores the read address signal and a stride adder which computes the next read address signal by adding the read address signal to a selected stride signal. The read address generator further includes a stride multiplexor for providing the selected stride signal. The stride multiplexor has at least two stride inputs which receive stride signals corresponding to the appropriate stride values for error diffusion mode and halftone mode. The stride multiplexor includes a control input tied to a stride select signal which indicates either the error diffusion or the halftone mode. A reset multiplexor provides the capability to set the read address signal either to a predetermined starting read address signal value or to the next read address signal computed by the stride adder. The reset multiplexor has a control input tied to a reset signal.
These and other aspects, features, and advantages of the present invention are fully discussed in the Detailed Description of the Invention.